package weka.classifiers.trees.IIDT;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;

import weka.core.converters.ConverterUtils.DataSource;
import weka.classifiers.Classifier;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.NoSupportForMissingValuesException;

public class IIDT extends Classifier {

	private static final long serialVersionUID = -8142396177479263562L;
	
	static String inputFile = "2foldXOR.arff";

	boolean PRINT_TO_FILE = true;

	enum WorkingClassifier{
		RANDOM, LSID3, LOOK_AHEAD
	}

	boolean NOT_INTERRUPTED = true;
	long maxRunTime = 1000000000L * 4;
	double g = 0;                                // granularity parameter
	WorkingClassifier classifierType = WorkingClassifier.LSID3;

	IIDTTreeClass tree = null;


	/**
	 * Builds IIDT classifier.
	 *
	 * @param data the training data
	 * @exception Exception if classifier can't be built successfully
	 */
	@Override
	public void buildClassifier(Instances data) throws Exception {

		// can classifier handle the data?
		getCapabilities().testWithFail(data);

		// remove instances with missing class
		data = new Instances(data);
		data.deleteWithMissingClass();

		makeTree(data);		
	}

	/**
	 * Classifies a given test instance using the decision tree.
	 *
	 * @param instance the instance to be classified
	 * @return the classification
	 * @throws Exception 
	 */
	public double classifyInstance(Instance instance) 
			throws Exception {

		if (instance.hasMissingValue()) {
			throw new NoSupportForMissingValuesException("IIDT classifier: no missing values, "
					+ "please.");
		}
		return tree.classifyInstance(instance);
	}

	/**
	 * Method for building an IIDT classifier decision tree.
	 *
	 * @param data the training data
	 * @exception Exception if decision tree can't be built successfully
	 */
	private void makeTree(Instances data) throws Exception{

		tree = new LookAheadClassifier();
		tree.buildClassifier(data);	

		System.out.println("");     
		System.out.println("");     
		System.out.println("----- Training classifier -----");    
		System.out.println(tree.toString());    
		System.out.println("");     
		System.out.println("");   

		long startTime = System.nanoTime();
		long currentTime = startTime;

		ArrayList<Long> time = new ArrayList<Long>();
		ArrayList<Integer> numberOfLeaves = new ArrayList<Integer>();

		long timeInterval = maxRunTime;

		while(NOT_INTERRUPTED){
			long deltaTime = currentTime - startTime;
			time.add(deltaTime);
			numberOfLeaves.add(tree.getNLeaves());

			IIDTTreeClass node = chooseNode(g);
			int r = node.getNextR();

			IIDTTreeClass enhancedNode;
			switch(classifierType){
			case RANDOM: enhancedNode = new LookAheadClassifier(r-1); break;
			case LSID3: enhancedNode = new LSID3(r); break;
			case LOOK_AHEAD: enhancedNode = new LookAheadClassifier(r-1); break;
			default: enhancedNode = new LookAheadClassifier(r-1);
			}

			enhancedNode.buildClassifier(node.getExamples());
			

			System.out.println("");     
			System.out.println("");     
			System.out.println("----- Enhanced node -----");    
			System.out.println(enhancedNode.toString());    
			System.out.println("");     
			System.out.println(""); 
			

			int evaluateNode = evaluate(node);
			int evaluateEnhancedNode = evaluate(enhancedNode);

			if(evaluateNode > evaluateEnhancedNode){
				replace(node, enhancedNode);
			}
			else{
				incrementSubtreeR(node);
			}
			currentTime = System.nanoTime();

			long endTime = System.nanoTime();
			if(endTime - startTime > timeInterval){
				NOT_INTERRUPTED = false;
			}		
		}

		String outputFileName = "out.txt";
		createFile(outputFileName);
		PrintStream ps = new PrintStream(new FileOutputStream(outputFileName));
		for(int i=0; i<time.size(); i++){
			ps.println(time.get(i).toString()+","+numberOfLeaves.get(i).toString());
		}
		ps.close();

	}

	private void incrementSubtreeR(IIDTTreeClass node) {
		int nextR = node.getNextR();

		setSubtreeR(node, nextR);		
	}

	private void setSubtreeR(IIDTTreeClass node, int r) {
		if(node.getNextR() > r){
			return;
		}
		node.setR(r);
		if(!node.isLeaf()){
			IIDTTreeClass[] successors = node.getSuccessors();
			for(IIDTTreeClass s:successors){
				setSubtreeR(s, r);
			}
		}

	}

	IIDTTreeClass chooseNode(double g){
		int nAtt = tree.getExamples().numAttributes() - 1;
		int nAnc = tree.getAncestorsNumber();
		int numUnusedAttributes = nAtt - nAnc;

		int _lastR = tree.getLastR();
		int _nInstances = tree.getExamples().numInstances();

		double maxCost = _lastR*_nInstances*
				numUnusedAttributes*numUnusedAttributes*numUnusedAttributes;		

		//		double maxCost = 
		//				tree.getLastR()*tree.getExamples().numInstances()*
		//				numUnusedAttributes*numUnusedAttributes*numUnusedAttributes;		


		return findBestNode(tree, g, maxCost);
	}

	IIDTTreeClass findBestNode(IIDTTreeClass root, double g, double maxCost){
		if(root.isLeaf()){
			return root;
		}else if(root.getHeight() <= 3){
			return root;			
		}else{
			IIDTTreeClass bestNode = root;
			double maxUnode = root.getUnode();

			IIDTTreeClass[] successors = root.getSuccessors();
			for(IIDTTreeClass s:successors){
				IIDTTreeClass subtreeBestNode = findBestNode(s, g, maxCost);

				double costNode = subtreeBestNode.getCostNode();				
				double costRatio = costNode/maxCost;

				if(costRatio > g){
					double subtreeUnode = subtreeBestNode.getUnode();
					if(subtreeUnode > maxUnode){
						maxUnode = subtreeUnode;
						bestNode = subtreeBestNode;
					}
				}
			}
			return bestNode;
		}		
	}

	int evaluate(IIDTTreeClass tree){
		return tree.getNLeaves();
	}

	void replace(IIDTTreeClass node, IIDTTreeClass enhancedNode){
		if(this.tree == node){
			this.tree = enhancedNode;
			return;
		}

		IIDTTreeClass parent = node.getParent();
		IIDTTreeClass[] parentSuccessors = parent.getSuccessors();

		for(int i=0; i<parentSuccessors.length; i++){
			if(parentSuccessors[i] == node){
				parentSuccessors[i] = enhancedNode;
				enhancedNode.setParent(parent);
				enhancedNode.setAncestors(node.getAncestors());
				break;
			}
		}

		int deltaNNodes = enhancedNode.getNNodes() - node.getNNodes();
		int deltaNLeaves = enhancedNode.getNLeaves() - node.getNLeaves();


		while(!node.isRoot()){
			parent.setNNodes(parent.getNNodes() + deltaNNodes);
			parent.setNLeaves(parent.getNLeaves() + deltaNLeaves);


			parentSuccessors = parent.getSuccessors();
			int maxHeight = - 1;
			for(IIDTTreeClass s:parentSuccessors){
				int sHeight = s.getHeight();
				if(sHeight > maxHeight){
					maxHeight = sHeight;
				}
			}
			parent.setHeight(maxHeight + 1);

			node = node.getParent();
			parent = node.getParent();
		}		
	}

	/**
	 * Prints the decision tree.
	 *
	 * @return a textual description of the classifier
	 */
	public String toString() {
		return "IIDT classifier\n\n" + tree.toString();
	}

	// This method creates a new file named 'fileName',
	// If a file by that name already exists it will be replaced
	private static void createFile(String fileName) throws IOException {
		File f;
		f = new File(fileName);
		if(f.exists()) {
			f.delete();
		}
		f.createNewFile();
	}

	public static void main(String[] args) throws Exception {
		String inputFileName = inputFile;

		IIDT classifier = new IIDT();

		DataSource source = null;

		try {
			source = new DataSource(inputFileName);
		} catch (Exception e) {
			throw new Exception("Can't open file " + e.getMessage() + '.');
		}
		int nAtt = source.getStructure().numAttributes();
		Instances inst = source.getDataSet(nAtt - 1);
		classifier.buildClassifier(inst);

		//		runClassifier(classifier, args);

		System.out.println("");     
		System.out.println("");     
		System.out.println("----- Training classifier -----");    
		System.out.println(classifier.toString());    
		System.out.println("");     
		System.out.println("");   
	}

}
